package z_exam;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/7 19:28
 */
public class Test6 {

    public static int computeSimlarity(String A_Str, String B_Str){
        HashMap<String, Integer> hashMap = new HashMap<>();
        HashMap<String, Integer> hashMapA = new HashMap<>();
        HashMap<String, Integer> hashMapB = new HashMap<>();
        String[] A_Str_Split = A_Str.split(" ");
        String[] B_Str_Split = B_Str.split(" ");
        for (int i = 0; i < A_Str_Split.length; i++) {
            hashMap.put(A_Str_Split[i], hashMap.getOrDefault(A_Str_Split[i], 0) + 1);
            hashMapA.put(A_Str_Split[i], hashMapA.getOrDefault(A_Str_Split[i], 0) + 1);
        }
        for (int i = 0; i < B_Str_Split.length; i++) {
            hashMap.put(B_Str_Split[i], hashMap.getOrDefault(B_Str_Split[i], 0) + 1);
            hashMapB.put(B_Str_Split[i], hashMapB.getOrDefault(B_Str_Split[i], 0) + 1);
        }
//            向量化表示
        StringBuffer A_Vec = new StringBuffer();
        StringBuffer B_Vec = new StringBuffer();
        Set<String> keys = hashMap.keySet();
        for (String key : keys){
            A_Vec.append(hashMapA.getOrDefault(key, 0));
            B_Vec.append(hashMapB.getOrDefault(key, 0));
        }
        String A = A_Vec.toString();
        String B = B_Vec.toString();
        int i = 0;
        int j = 0;
        int num = 0;
        while (i < A.length()){
            int numA = A.charAt(i) - '0';
            int numB = B.charAt(j) - '0';
            num += numA * numB;
            i++;
            j++;
        }
        int result = num;
        return result;
    }


    /**
     * 每次你可以爬 1 或 2 个台阶。
     * dp[i]表示爬到第i层所需要的层数
     */
    public int climbStairs(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i < dp.length; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }


    /**
     * cost[i] 是从楼梯第 i 个台阶向上爬需要支付的最小费用。 选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
     * dp[i]：表示到达第i层所需要的费用
     * dp[i] = Math.max(dp[i-1] + cost[i-1], dp[i-2]+cost[i-2])
     * @param cost
     * @return
     */
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i < n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }

    /**
     * 每次只能向下或者向右移动一步。
     * dp[i][j]表示到达i,j位置有多少条路径
     * dp[i][j] = dp[i-1][j] + dp[i][j-1]
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * dp[i][j]表示到达i,j的路径个数
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[][] dp = new int[n][m];
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[i][0] == 0) {
                dp[i][0] = 1;
            }else{
                break;
            }
        }
        for (int j = 0; j < m; j++) {
            if (obstacleGrid[0][j] == 0) {
                dp[0][j] = 1;
            }else{
                break;
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][m - 1];
    }

    /**
     * n, 将其拆分为 k 个正整数 的和
     * dp[i]表示i拆分k份，乘积和最大为dp[i]
     * @param n
     * @return
     */
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }

    /**
     * dp[i]表示节点个数为n的二叉搜索树的个数
     * @param n
     * @return
     */
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }

    /**
     * 这个数组分割成两个子集，使得两个子集的元素和相等。个数可以不相等
     * dp[i]表示容量为i的背包装的最大价值，物品的重量和价值一样
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        //物品
        for (int i = 0; i < nums.length; i++) {
            //表示背包容量
            for (int j = target; j >= nums[i]; j--) {
                //当前物品i放或者不放
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }


    /**
     * dp[i]表示容量为i的背包最大价值
     * @param stones
     * @return
     */
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i = 0; i < stones.length; i++) {
            sum += stones[i];
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for (int i = 0; i < stones.length; i++) {
            for (int j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] * 2;
    }

    /**
     * dp[i]表示背包容量为i时的方案数
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if ((sum + target) % 2 != 0 || sum + target < 0) {
            return 0;
        }
        int left = (sum + target) / 2;
        int[] dp = new int[left + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = left; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[left];
    }

    /**
     * dp[i][j]表示str剩i个0，n个1的最大子集长度
     * @param strs
     * @param m
     * @param n
     * @return
     */
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < len; i++) {
            String s = strs[i];
            int zero = 0;
            int one = 0;
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) == '0') {
                    zero++;
                }else{
                    one++;
                }
            }
            //相当于背包重量
            for (int j = m; j >=zero; j--) {
                for (int k = n; k >= one; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - zero][k - one] + 1);
                }
            }
        }
        return dp[m][n];
    }

    /** 假设每一种面额的硬币有无限个。返回可以凑成总金额的硬币组合数
     * dp[i]表示凑成amount金额的硬币组合数
     * @param amount
     * @param coins
     * @return
     */
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        //物品
        for (int i = 0; i < coins.length; i++) {
            //背包容量
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }

    /**
     * dp[i]表示总和为 i 的元素组合的个数。
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        //背包容量
        for (int i = 0; i <= target; i++) {
            //物品
            for (int j = 0; j < nums.length; j++) {
                if (i - nums[j] >= 0) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }

    /**
     * 改为：一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？
     * [1,2,3,4,5,6,7,...m]
     * dp[i]表示到达楼顶的方案数
     * @param n
     * @return
     */
    public int climbStairs1(int n, int m) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        //背包
        for (int i = 0; i <= n; i++) {
            //物品
            for (int j = 1; j <= m; j++) {
                if (i - j >= 0) {
                    dp[i] += dp[i - j];
                }
            }
        }
        return -1;
    }


    /**
     * 计算并返回可以凑成总金额所需的 最少的硬币个数 。
     * dp[i]表示凑够i的最少硬币个数  完全背包+组合
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        //物品
        for (int j = 0; j < coins.length; j++) {
            //背包
            for (int i = coins[j]; i <= amount; i++) {
                if (dp[i - coins[j]] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

    /**
     * dp[i]表示和为i的完全平方数的最小数量  组合，完全背包
     * @param n
     * @return
     */
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        //物品
        for (int i = 1; i <= n; i++) {
            //完全平方数
            int sqrt = (int)Math.sqrt(i);
            if (sqrt * sqrt == i) {
                for (int j = i; j <= n; j++) {
                    dp[j] = Math.min(dp[j], dp[j - i] + 1);
                }
            }
        }
        return dp[n];
    }

    /**
     * 完全背包，排列|组合都可以
     * dp[i]长度为i的s字符串能否被拼接而成。->dp[i]表示长度为i的字符串能否拆分为字典中的单词
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        //背包容量
        for (int i = 1; i <= n; i++) {
            //字符串拆分（从0开始拆）
            for (int j = 0; j <= i - 1; j++) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                }
            }
        }
        return dp[n];
    }

    /**
     * dp[i]：偷到下标为i的屋子偷到最高的金额
     * @param nums
     * @return
     */
    public int rob1(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 2]);
        }
        return dp[n - 1];
    }

    /**
     * 不包括左，不包括右
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        } else if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        //包括第1个
        for (int i = 2; i < n - 1; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        int max = dp[n - 2];
        dp[1] = nums[1];
        dp[2] = Math.max(nums[1], nums[2]);
        for (int i = 3; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return max > dp[n - 1] ? max : dp[n - 1];
    }

    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }

    public int rob(TreeNode root) {
        int[] result = dfs(root);
        return Math.max(result[0], result[1]);
    }

    /**
     * dp[2]  dp[0]代表该节点不偷时的最大值，dp[1]代表该节点偷时的最大值
     * @param root
     * @return
     */
    private int[] dfs(TreeNode root) {
        int[] dp = new int[2];
        if (root == null) {
            return dp;
        }
        int[] left = dfs(root.left);
        int[] right = dfs(root.right);
        dp[1] = root.val;
        //该节点不选
        dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        dp[1] = left[0] + right[0];
        return new int[]{dp[0], dp[1]};
    }

    public static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries){
        Map<String, Map<String, Double>> hash = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            List<String> edges = equations.get(i);
            hash.computeIfAbsent(edges.get(0), k -> new HashMap<>()).put(edges.get(1), values[i]);
            hash.computeIfAbsent(edges.get(1), k -> new HashMap<>()).put(edges.get(0), 1 / values[i]);
        }
        double[] result = new double[queries.size()];
        int count = 0;
        for (List<String> edges : queries) {
            String start = edges.get(0);
            String end = edges.get(1);
            if (!hash.containsKey(start) || !hash.containsKey(end)) {
                result[count++] = -1.0;
            }else{
                result[count++] = dfs(hash, start, end, new HashSet<>(),1.0);
            }
        }
        return result;
    }

    private static double dfs(Map<String,Map<String,Double>> hash, String start, String end, HashSet<String> visited, double result) {
        //访问过
        if (!visited.add(start)) {
            return -1.0;
        }
        //到终点了，返回结果值
        if (start.equals(end)) {
            return result;
        }
        Map<String, Double> stringDoubleMap = hash.get(start);
        Set<String> strings = stringDoubleMap.keySet();
        for (String node : strings) {
            //result * stringDoubleMap.get(node) 这样写下一次循环也相当于result（隐式回溯）
            double dfs = dfs(hash, node, end, visited, result * stringDoubleMap.get(node));
            if (dfs != -1.0) {
                return dfs;
            }
        }
        return -1.0;
    }

    /**
     * dp[i][j]表示dp[i][0] dp[i][1] 表示第i天保持状态为j时有多少钱
     * dp[i][0]买 dp[i][1]卖
     * dp[i][0] = Math.max(dp[i-1][0], -prices[i]) 当天买，不买
     * dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]+prices[i])  当天卖
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int day = prices.length;
        int[][] dp = new int[day][2];
        dp[0][0] = -prices[0];
        for (int i = 1; i < day; i++) {
            //当前为买状态 -> 前一天也为买或者，当天买
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            //当前为卖状态 -> 前一天也为卖，当天卖
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[day - 1][1];
    }

    /**
     * dp[i][j]表示第i天保持状态j时的最多有多少钱
     * 买：当天不买，保持前一天买的状态；当天买
     * dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i])
     * 卖：当天不卖，保持前一天卖的状态；当天卖
     * dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i])
     * @param prices
     * @return
     */
    public int maxProfit1(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < len; i++) {
            //买：当天不买，保持前一天买的状态；当天买
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            //卖：当天不卖，保持前一天卖的状态；当天卖
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[len - 1][1];
    }

    /**
     * dp[i][j]表示第i天保持状态j时手上最多剩多少钱（你最多可以完成两笔交易。）
     * 状态：第一次买0、第一次卖1、第二次买2、第二次卖3
     * 买：当天不买，保持昨天买的状态；当天买；
     * dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i])
     * 第二次卖：当天不卖
     * dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] + prices[i])
     * 第二次买
     * dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] - prices[i])
     * dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] + prices[i])
     *
     * dp[
     * @param prices
     * @return
     */
    public int maxProfit11(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][4];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        dp[0][3] = 0;
        for (int i = 1; i < len; i++) {
            //第一次买
            dp[i][0] = Math.max(dp[i - 1][0], - prices[i]);
            //第一次卖
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
            //第二次买
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] - prices[i]);
            //第二次卖
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] + prices[i]);
        }
        return Math.max(dp[len - 1][1], dp[len - 1][3]);
    }


    /**
     * dp[i][j]表示第i天保持状态i时最多有多少钱
     * 第一次买
     * dp[i][0] = Math.Max(dp[i-1][0], -prices[i])
     * 第二次卖
     * d[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i])
     *   ...
     *   ...
     * @param k
     * @param prices
     * @return
     */
    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        if (len == 0) {
            return 0;
        }
        int[][] dp = new int[len][2 * k];
        //初始化买
        for (int j = 0; j < 2 * k; j += 2) {
            dp[0][j] = -prices[0];
        }
        int max = 0;
        for (int i = 1; i < len; i++) {
            //第一天2*k个状态
            for (int j = 0; j < 2 * k; j+=2) {
                if (j == 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], - prices[i]);
                    dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                    dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
                }
                if (i == len - 1 && dp[i][j + 1] > max) {
                    max = dp[i][j + 1];
                }
            }
        }
        return max;
    }

    /**
     * dp[i][j]表示第i天保持状态j时最多有多少钱
     * //买
     * dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i], dp[i-1][2])
     * //卖
     * dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i])
     * //冷冻期（只有当前一天是卖的时候才是冷冻期）
     * dp[i][2] = dp[i-1][1]
     * //过了冷冻期的那几天
     * dp[i][3] = dp[i-1][2]
     * @param prices
     * @return
     */
    public int maxProfit111(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][4];
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++) {
            //买
            dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][2] - prices[i], dp[i - 1][3] - prices[i]));
            //卖
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
            //冷冻期
            dp[i][2] = dp[i - 1][1];
            //过了冷冻期
            dp[i][3] = dp[i - 1][2];
        }
        return dp[n - 1][1];
    }

    /**
     * dp[i][j]表示第i天保持状态j时最多有多少钱
     * //第一次买
     * dp[i][0]
     * //第一次卖
     * dp[i][1]
     * @param prices
     * @param fee
     * @return
     */
    public int maxProfit(int[] prices, int fee) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = -prices[0] - fee;
        for (int i = 1; i < len; i++) {
            //买
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i] - fee);
            //卖
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[len - 1][1];
    }


//    public static void main(String[] args) {
//        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd");
//        Calendar instance = Calendar.getInstance();
//        instance.setTime(new Date());
//        instance.add(Calendar.DAY_OF_YEAR, 186);
//        String format = simpleDateFormat.format(instance.getTime());
//        System.out.println(format);
//        List<TreeNode> list = new ArrayList<>();
//        list.add(null);
//        list.add(new TreeNode(-1));
//        System.out.println(list);
//    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        System.out.println(s);
        sc.nextLine();
        String s1 = sc.nextLine();
        System.out.println(s1);
        int d = sc.nextInt();
        System.out.println(d);
        int d1 = sc.nextInt();
        System.out.println(d1);
    }
}
